package personal_exercise;

import model.ListNode;
import model.Node;

import java.util.*;

public class Demo5 {


    // JZ73 翻转单词序列
    public String ReverseSentence(String str) {
        StringBuilder res = new StringBuilder();
        int right = str.length() - 1;
        int left = right;
        while (right >= 0) {
            while (left >= 0 && str.charAt(left) != ' ') left--;
            String s = str.substring(left + 1, right + 1);
            res.append(s);
            right = --left;
            if (right >= 0) res.append(' ');
        }
        return res.toString();
    }


    // JZ21 调整数组顺序使奇数位于偶数前面(一)
    public int[] reOrderArray(int[] array) {
        int n = array.length;
        int[] res = new int[n];
        int left = -1, right = n;
        for (int x : array) {
            if (x % 2 == 1) {
                res[++left] = x;
            } else if (x % 2 == 0) {
                res[--right] = x;
            }
        }
        for (left = right, right = n - 1; left < right; left++, right--) {
            int tmp = res[left];
            res[left] = res[right];
            res[right] = tmp;
        }
        return res;
    }


    // JZ50 第一个只出现一次的字符
    public int FirstNotRepeatingChar(String str) {
        int[] count = new int[128];
        for (char ch : str.toCharArray()) {
            count[ch]++;
        }

        for (int i = 0; i < str.length(); i++) {
            if (count[str.charAt(i)] == 1) return i;
        }
        return -1;
    }


    // JZ61 扑克牌顺子
    public boolean IsContinuous(int[] numbers) {
        // 只要相同的数字(非0)出现两次,即为不连续
        boolean[] flag = new boolean[14];
        int max = -1, min = 14, zero = 0;
        for (int x : numbers) {
            if (x == 0) {
                zero++;
            } else {
                if (flag[x]) return false;
                flag[x] = true;
                if (x > max) max = x;
                if (x < min) min = x;
            }
        }
        if (max - min - 1 > 3) return false;
        return true;
    }


    // JZ75 字符流中第一个不重复的字符
    public class Solution {
        StringBuilder stb = new StringBuilder();
        int[] vis = new int[128];

        //Insert one char from stringstream
        public void Insert(char ch) {
            stb.append(ch);
            vis[ch]++;
        }

        //return the first appearence once char in current stringstream
        public char FirstAppearingOnce() {
            for (int i = 0; i < stb.length(); i++) {
                if (vis[stb.charAt(i)] == 1) return stb.charAt(i);
            }
            return '#';
        }

    }


    // JZ62 孩子们的游戏(圆圈中最后剩下的数)
    public int LastRemaining_Solution (int n, int m) {
        List<Integer> l = new ArrayList<>();
        for (int i = 0; i < n; i++) l.add(i);

        int cur = 0;
        while (l.size() > 1) {
            cur = (cur + m - 1) % l.size();
            l.remove(cur);
        }
        return l.get(0);
    }



    // JZ58 左旋转字符串
    public String LeftRotateString (String str, int n) {
        if (str == null) return str;
        int len = str.length();
        if (len == 0 || n % len == 0) return str;

        n %= len;
        StringBuilder res = new StringBuilder();
        for (int i = n; i < len; i++) {
            res.append(str.charAt(i));
        }
        for (int i = 0; i < n; i++) {
            res.append(str.charAt(i));
        }
        return res.toString();
    }



    // JZ57 和为S的两个数字
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        // 存储前面遍历过的数
        Set<Integer> hash = new HashSet<>();
        for (int x : array) {
            if (hash.contains(sum - x)) {
                ArrayList<Integer> res = new ArrayList<>();
                res.add(x);
                res.add(sum - x);
                return res;
            }
            hash.add(x);
        }
        return new ArrayList<Integer>();
    }




    // JZ74 和为S的连续正数序列
    public ArrayList<ArrayList<Integer>> FindContinuousSequence (int sum) {
        // 滑动窗口
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int left = 1, right = 1;
        int tmpSum = 0;
        for (; right<= (sum + 1) / 2; right++) {
            tmpSum += right;
            while (tmpSum > sum) {
                tmpSum -= left++;
            }
            if (tmpSum == sum) {
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = left; i <= right; i++) {
                    list.add(i);
                }
                if (list.size() > 1) res.add(list);
            }
        }
        return res;
    }



    // LCR 155. 将二叉搜索树转化为排序的双向链表
    private Node prev;
    private Node res;

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;

        dfs(root);
        res.left = prev;
        prev.right = res;
        return res;
    }
    private void dfs(Node node) {
        if (node == null) return;
        dfs(node.left);
        if (prev != null) {
            prev.right = node;
            node.left = prev;
        } else {
            res = node;
        }
        prev = node;
        dfs(node.right);
    }



    //  LCR 081. 组合总和
//    private List<List<Integer>> res;
//    private List<Integer> path;
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        res = new ArrayList<>();
//        path = new ArrayList<>();
//        Arrays.sort(candidates);
//
//        dfs(candidates, 0, target);
//        return res;
//    }
//    private void dfs(int[] candidates, int pos, int target) {
//        if (target == 0) {
//            res.add(new ArrayList<>(path));
//            return;
//        }
//
//        for (int i = pos; i < candidates.length; i++) {
//            if (target - candidates[i] < 0) break;
//            path.add(candidates[i]);
//            dfs(candidates, i, target - candidates[i]);
//            path.remove(path.size() - 1);
//        }
//    }




    // 37. 解数独
    private boolean[][] rows;
    private boolean[][] cols;
    private boolean[][][] grid;

    public void solveSudoku(char[][] board) {
        rows = new boolean[9][10];
        cols = new boolean[9][10];
        grid = new boolean[3][3][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    cols[j][num] = rows[i][num] = grid[i/3][j/3][num] = true;
                }
            }
        }

        dfs(board);
    }
    private boolean dfs(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') continue;

                for (int k = 1; k <= 9; k++) {
                    if (!cols[j][k] && !rows[i][k] && !grid[i/3][j/3][k]) {
                        board[i][j] = (char)(k + '0');
                        cols[j][k] = rows[i][k] = grid[i/3][j/3][k] = true;
                        boolean b = dfs(board);
                        if (b) return true;

                        cols[j][k] = rows[i][k] = grid[i/3][j/3][k] = false;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }



    // 375. 猜数字大小 II
    private int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n + 1][n + 1];
        return dfs(1, n);
    }
    private int dfs(int left, int right) {
        if (left >= right) return 0;
        if (memo[left][right] != 0) return memo[left][right];

        int ret = Integer.MAX_VALUE;
        for (int i = left; i <= right; i++) {
            ret = Math.min(ret, Math.max(dfs(left, i - 1), dfs(i + 1, right)) + i);
        }
        memo[left][right] = ret;
        return ret;
    }



    // 740. 删除并获得点数
    public int deleteAndEarn(int[] nums) {
        int max = 0;
        for (int x : nums) {
            if (x > max) max = x;
        }
        int[] arr = new int[max + 1];
        for (int x : nums) {
            arr[x] += x;
        }

        int[] dp = new int[max + 1];
        dp[1] = arr[1];
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[max];
    }


    // 23. 合并 K 个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return mergeSort(lists, 0, lists.length - 1);
    }

    private ListNode mergeSort(ListNode[] lists, int left, int right) {
        if (left >= right) return lists[left];

        int mid = (left + right) / 2;
        ListNode l1 = mergeSort(lists, left, mid);
        ListNode l2 = mergeSort(lists, mid + 1, right);

        ListNode res = new ListNode();
        ListNode tail = res;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        if (l1 != null) tail.next = l1;
        if (l2 != null) tail.next = l2;
        return res.next;
    }


    // 213. 打家劫舍 II
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(rob(nums, 2, n - 2) + nums[0], rob(nums, 1, n - 1));
    }
    private int rob(int[] nums, int x, int y) {
        if(x > y) return 0;

        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        f[x] = nums[x];
        for(int i = x + 1; i <= y; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        return Math.max(f[y], g[y]);
    }



    // kotori和抽卡（二）
    public static void main2(String[] argv) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        double res = 1.0f;
        for (int i = n; i >= (n - m + 1); i--) res *= i;
        for (int i = m; i >= 1; i--) res /= i;
        res *= Math.pow(0.8, m);
        res *= Math.pow(0.2, n - m);
        System.out.printf("%.4f\n", res);
    }




    // ruby和薯条
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), l = in.nextInt(), r = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();
        Arrays.sort(arr);

        // 排序 + 前缀和 + 滑动窗口
        System.out.println(find(r, arr) - find(l - 1, arr));
    }
    // 找到身高差值在[0 - num]的数对个数
    private static long find(int num, int[] arr) {
        long ret = 0, n = arr.length;
        for (int l = 0, r = 0; r < n; r++) {
            while (arr[r] - arr[l] > num) {
                l++;
            }
            ret += r - l;
        }
        return ret;
    }



    // AB27 循环汉诺塔
    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int MOD = 1000000007;

        long prev1 = 1, prev2 = 2;
        long res1 = 1, res2 = 2;
        for (int i = 2; i <= n; i++) {
            res1 = (2 * prev2 + 1) % MOD;
            res2 = ((2 * prev2 + 2) % MOD + prev1) % MOD;
            prev1 = res1;
            prev2 = res2;
        }
        System.out.println(res1 + " " + res2);
    }



    // 最小差值
    public int minDifference (int[] a) {
        Arrays.sort(a);

        long res = Integer.MAX_VALUE;
        for (int i = 0, n = a.length; i < n - 1; i++) {
            if (a[i] == a[i + 1]) return 0;
            res = Math.min(res, (long)a[i + 1] - a[i]);
        }
        return (int)res;
    }




    // dd爱科学1.0
    public static void main5(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[] arr = in.next().toCharArray();

        // 寻找最长非递减子序列(贪心 + 2分)
        List<Character> res = new ArrayList<>();
        for (char ch : arr) {
            if (res.isEmpty() || ch >= res.get(res.size() - 1)) {
                res.add(ch);
                continue;
            }

            // 寻找值小于等于 ch 的最右端点
            int left = 0, right = res.size() - 1, mid;
            while (left < right) {
                mid = left + (right - left) / 2;
                if (res.get(mid) > ch) right = mid;
                else left = mid + 1;
            }
            res.set(left, ch);
        }
        System.out.println(n - res.size());
    }



    // kotori和素因子
    private static int ret = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();

        dfs(arr, 0, 0, new boolean[1010]);
        if (ret > 10000) ret = -1;
        System.out.println(ret);
    }
    private static void dfs(int[] arr, int pos, int sum, boolean[] vis) {
        if (pos == arr.length) {
            ret = Math.min(ret, sum);
            return;
        }

        for (int i = 2; i <= arr[pos]; i++) {
            if (arr[pos] % i == 0 && isPrime(i) && !vis[i]) {
                vis[i] = true;
                dfs(arr, pos + 1, sum + i, vis);
                vis[i] = false;
            }
        }
    }
    private static boolean isPrime(int num) {
        double tmp = Math.sqrt(num);
        for (int i = 2; i <= tmp; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }



}
